#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 50005;

int n, q;
int a[N];
int f[N][20];
int g[N][20];

int main()
{
	freopen("st.in", "r", stdin);
	freopen("st.out", "w", stdout);
	
	scanf("%d%d", &n, &q);
	for(int i=1; i<=n; i++) scanf("%d", &a[i]);
	
	for(int i=1; i<=n; i++) f[i][0] = g[i][0] = a[i];
	for(int i=1, j=2; j<=n; i++, j*=2)
		for(int k=1; j+k-1<=n; ++k)
			f[k][i] = min(f[k][i-1], f[k+j/2][i-1]),
			g[k][i] = max(g[k][i-1], g[k+j/2][i-1]);
		
	for(int i=1, l, r; i<=q; i++)
	{
		scanf("%d%d", &l, &r);
		int p = int(log(r-l+1) / log(2) + 0.001);
		int mi = min(f[l][p], f[r-(1<<p)+1][p]);
		int ma = max(g[l][p], g[r-(1<<p)+1][p]);
		printf("%d\n", ma - mi);
	}
	
	return 0;
}
